#include <bits/stdc++.h>
using namespace std;

// 暴力做法 o(n*N)
class Compare
{
public:
    bool operator()(const vector<int> &a, const vector<int> &b)
    {
        if (a[0] == b[0])
        {
            return a[1] < b[1];
        }
        return a[0] < b[0];
    }
};
class Solution
{
public:
    int maxEnvelopes(vector<vector<int>> &envelopes)
    {
        sort(envelopes.begin(), envelopes.end(), Compare());
        int n = envelopes.size();
        vector<int> dp(n, 1);
        int ret = 1;
        for (int i = 1; i < n; i++)
        {
            int tem = 0;
            for (int j = 0; j < i; j++)
            {
                if (envelopes[i][0] > envelopes[j][0] && envelopes[i][1] > envelopes[j][1])
                {
                    tem = max(dp[j], tem);
                }
            }
            dp[i] += tem;
            ret = max(ret, dp[i]);
        }
        return ret;
    }
};
int main()
{

    return 0;
}

// 优化做法 贪心加二分查找
// 把区间排序 左端点相同，按照右端点降序排序
// 这样就是问题转化为求区间=右端点的最长递增子序列问题
// len数组记录长度位i的数字的最小值，每次来了一个数x我们要把到插入到len数组的位置上
// 插入的位置位大于等于x的最左端点 如果找不到说明len数组没有大于x的数字，此时我们要新增一个长度存储改值
//O(N*logN)
class Compare
{
public:
    bool operator()(const vector<int> &a, const vector<int> &b)
    {
        if (a[0] == b[0])
        {
            return a[1] > b[1];
        }
        return a[0] < b[0];
    }
};
class Solution
{
public:
    int maxEnvelopes(vector<vector<int>> &envelopes)
    {
        sort(envelopes.begin(), envelopes.end(), Compare());
        int n = envelopes.size();
        vector<int> len(n, 0); // key值就是长度，val值是数字小的那个
        int index = 0;
        len[0] = envelopes[0][1];
        for (int i = 1; i < n; i++)
        {
            int val = envelopes[i][1];
            // 二分查找此时val的插入位置
            // 如果val值严格大于此时len数组里面的val值就返回对应val下标+1
            // 如果小于等于此时的val值就直接覆盖len数组的val值即可
            // 二分查找严格大于val的最左边
            int left = 0, right = index, ans = -1;
            while (left <= right)
            {
                int mid = (right - left) / 2 + left;
                if (len[mid] >= val)
                {
                    ans = mid;
                    right = mid - 1;
                }
                else
                {
                    left = mid + 1;
                }
            }
            if (ans == -1)
            {
                len[++index] = val;
            }
            else
            {
                len[ans] = val;
            }
        }
        return index + 1;
    }
};